#include <iostream>

using namespace std;
using ll = long long;

ll cost_to_make(const string& s, char want) {
	int n = (int) s.size();
	int l = 0, r = n - 1;
	ll ans = 0;
	while (l <= r) {
		if (s[l] != want) {
			ans += 1;
			l++;
			continue;
		}
		if (s[r] != want) {
			ans += 1;
			r--;
			continue;
		}
		int i = l;
		while (i <= r && s[i] == want) i++;
		if (i > r) break;
		int dl = i - l;
		
		int j = r;
		while (j >= l && s[j] == want) j--;
		int dr = r - j;
		
		if (dl <= dr) {
			ans += 2LL * dl + 1;
			l = i + 1;
		} else {
			ans += 2LL * dr + 1;
			r = j - 1;
		}
	}
	
	return ans;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int t;
	if (!(cin >> t)) return 0;
	while (t-- > 0) {
		int N; string S;
		cin >> N >> S;

		ll ans0 = cost_to_make(S, '0');
		ll ans1 = cost_to_make(S, '1');
		cout << min(ans0, ans1) << endl;
	}
	return 0;
}


